package com.shm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 1489. 找到最小生成树里的关键边和伪关键边
 * 给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1 ，同时还有一个数组 edges ，其中 edges[i] = [fromi, toi, weighti] 表示在 fromi 和 toi 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集，它连接了所有节点且没有环，而且这些边的权值和最小。
 *
 * 请你找到给定图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。
 *
 * 请注意，你可以分别以任意顺序返回关键边的下标和伪关键边的下标。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
 * 输出：[[0,1],[2,3,4,5]]
 * 解释：上图描述了给定图。
 * 下图是所有的最小生成树。
 *
 * 注意到第 0 条边和第 1 条边出现在了所有最小生成树中，所以它们是关键边，我们将这两个下标作为输出的第一个列表。
 * 边 2，3，4 和 5 是所有 MST 的剩余边，所以它们是伪关键边。我们将它们作为输出的第二个列表。
 * 示例 2 ：
 *
 *
 *
 * 输入：n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
 * 输出：[[],[0,1,2,3]]
 * 解释：可以观察到 4 条边都有相同的权值，任选它们中的 3 条可以形成一棵 MST 。所以 4 条边都是伪关键边。
 *
 *
 * 提示：
 *
 * 2 <= n <= 100
 * 1 <= edges.length <= min(200, n * (n - 1) / 2)
 * edges[i].length == 3
 * 0 <= fromi < toi < n
 * 1 <= weighti <= 1000
 * 所有 (fromi, toi) 数对都是互不相同的。
 *
 * @author SHM
 */
public class FindCriticalAndPseudoCriticalEdges {
    /**
     * 前言
     * 要想解决本题，需要用到「最小生成树」以及对应求解最小生成树的「\texttt{Kruskal}Kruskal 算法」。
     *
     * 对上述算法和数据结构的讲解不是本篇题解的重点，因此这里希望读者在对掌握了这些知识点之后，再来尝试解决本题。
     *
     * 本篇题解中会给出两种算法，并且每种算法都默认读者已经掌握了对应的知识点：
     *
     * 方法一只需要枚举每一条边，并用略微修改的 \texttt{Kruskal}Kruskal 算法判断其是否是关键边或伪关键边；
     *
     * 方法二利用了 \texttt{Kruskal}Kruskal 算法的连通性性质，以及无向图找桥边的 \texttt{Tarjan}Tarjan 算法，即使在竞赛中也不算容易，仅供读者挑战自我。
     *
     * 方法一：枚举 + 最小生成树判定
     * 思路与算法
     *
     * 我们首先需要理解题目描述中对于「关键边」和「伪关键边」的定义：
     *
     * 关键边：如果最小生成树中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。也就是说，如果设原图最小生成树的权值为 \textit{value}value，那么去掉这条边后：
     *
     * 要么整个图不连通，不存在最小生成树；
     *
     * 要么整个图联通，对应的最小生成树的权值为 vv，其严格大于 \textit{value}value。
     *
     * 伪关键边：可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。也就是说，我们可以在计算最小生成树的过程中，最先考虑这条边，即最先将这条边的两个端点在并查集中合并。设最终得到的最小生成树权值为 vv，如果 v = \textit{value}v=value，那么这条边就是伪关键边。
     *
     * 需要注意的是，关键边也满足伪关键边对应的性质。因此，我们首先对原图执行 \texttt{Kruskal}Kruskal 算法，得到最小生成树的权值 \textit{value}value，随后我们枚举每一条边，首先根据上面的方法判断其是否是关键边，如果不是关键边，再判断其是否是伪关键边。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(m^2 \cdot \alpha(n))O(m
     * 2
     *  ⋅α(n))，其中 nn 和 mm 分别是图中的节点数和边数。我们首先需要对所有的边进行排序，时间复杂度为 O(m \log m)O(mlogm)。一次 \texttt{Kruskal}Kruskal 算法的时间复杂度为 O(m \cdot \alpha(n))O(m⋅α(n))，其中 \alphaα 是阿克曼函数的反函数。我们最多需要执行 2m + 12m+1 次 \texttt{Kruskal}Kruskal 算法，时间复杂度为 O(m^2 \alpha(n))O(m
     * 2
     *  α(n))，在渐进意义下大于排序的时间复杂度，因此前者可以忽略不计，总时间复杂度为 O(m^2 \cdot \alpha(n))O(m
     * 2
     *  ⋅α(n))。
     *
     * 空间复杂度：O(m + n)O(m+n)。在进行排序时，我们必须要额外存储每条边原始的编号，用来返回答案，空间复杂度为 O(m)O(m)。\texttt{Kruskal}Kruskal 算法中的并查集需要使用 O(n)O(n) 的空间，因此总空间复杂度为 O(m+n)O(m+n)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/solution/zhao-dao-zui-xiao-sheng-cheng-shu-li-de-gu57q/
     * @param n
     * @param edges
     * @return
     */
    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        int m = edges.length;
        int[][] newEdges = new int[m][4];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 3; j++) {
                newEdges[i][j] = edges[i][j];
            }
            newEdges[i][3] = i;
        }

        Arrays.sort(newEdges, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2]-o2[2];
            }
        });

        UnionFind uf = new UnionFind(n);
        int value = 0;
        for (int i = 0; i < m; i++) {
            if(uf.union(newEdges[i][0],newEdges[i][1])){
                value+=newEdges[i][2];
            }
        }

        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < 2; i++) {
            ans.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            UnionFind unionFind = new UnionFind(n);
            int v=0;
            for (int j = 0; j < m; j++) {
                if(i!=j&&unionFind.union(newEdges[j][0],newEdges[j][1])){
                    v+=newEdges[j][2];
                }
            }
            if(unionFind.setCount!=1||(unionFind.setCount==1&&v>value)){
                ans.get(0).add(newEdges[i][3]);
                continue;
            }

            unionFind = new UnionFind(n);
            unionFind.union(newEdges[i][0],newEdges[i][1]);
            v=newEdges[i][2];
            for (int j = 0; j < m; j++) {
                if(i!=j&&unionFind.union(newEdges[j][0],newEdges[j][1])){
                    v+=newEdges[j][2];
                }
            }
            if(v==value){
                ans.get(1).add(newEdges[i][3]);
            }
        }
        return ans;
    }

    class UnionFind{
        int[] parent;
        int setCount;
        int[] size;

        UnionFind(int n){
            parent = new int[n];
            size = new int[n];
            setCount = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        int find(int x){
            if(x!=parent[x]){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        boolean union(int x,int y){
            int newX = find(x);
            int newY = find(y);
            if(newX == newY){
                return false;
            }
            if(size[newX]<size[newY]){
                int tmp = size[newX];
                size[newX] = size[newY];
                size[newY] = tmp;
            }
            parent[newY] = newX;
            size[newX]+=size[newY];
            setCount--;
            return true;
        }

        boolean connect(int x,int y){
            int newX = find(x);
            int newY = find(y);
            return newX ==newY;
        }
    }
}
